class Solution {
    bool visited[9][9][9][9];
    int dirR[4][4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int dirB[4][4] = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
public:
    int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        // BFS广度优先搜索
        visited[a][b][c][d] = true;
        queue<vector<int>> q;
        q.push({a, b, c, d, 0});
        while(!q.empty())
        {
            queue<vector<int>> tmp(q);

            while(!tmp.empty())
            {
                vector<int> v = tmp.front();
                tmp.pop();
                int Rx = v[0], Ry = v[1], Bx = v[2], By = v[3], step = v[4];

                if((Rx == e && Ry == f) || (Bx == e && By == f))
                    return step;

                // 遍历车
                for(auto dir: dirR)
                {
                    int nrx = Rx + dir[0], nry = Ry + dir[1];
                    while(nrx >= 1 && nrx <= 8&& nry >= 1 && nry <= 8)
                    {
                        if(nrx == Bx && nry == By)
                            break;
                        if(nrx == e && nry == f)
                            return step + 1;
                        if(!visited[nrx][nry][Bx][By])
                        {
                            visited[nrx][nry][Bx][By] = true;
                            q.push({nrx, nry, Bx, By, step + 1});
                        }
                        
                        nrx += dir[0];
                        nry += dir[1];
                    }
                }

                // 遍历象
                for(auto dir: dirB)
                {
                    int nbx = Bx + dir[0], nby = By + dir[1];
                    while(nbx >= 1 && nbx <= 8 && nby >= 1 && nby <= 8)
                    {
                        if(nbx == Rx && nby == Ry)
                            break;
                        if(nbx == e && nby == f)
                            return step + 1;
                        if(!visited[Rx][Ry][nbx][nby])
                        {
                            visited[Rx][Ry][nbx][nby] = true;
                            q.push({Rx, Ry, nbx, nby, step + 1});
                        }

                        nbx += dir[0];
                        nby += dir[1];
                    }
                }
            }
        }
        return -1;
    }
};